#include "function.h"

//int wpl=0; //全局变量

//前序遍历(深度优先遍历)
int PreOrder(BiTree p,int deep)
{
    //静态局部变量只会初始化一次，与全局变量类似，只能在函数内访问，外部不能访问，访问需要返回
    static int wpl=0;
    if(p!=NULL)
    {
//        printf("element:%c--deep:%d\n",p->weight,deep); //先打印自身
        if(p->lchild==NULL&&p->rchild==NULL)
        {
            wpl=wpl+p->weight*deep;
        }
        PreOrder(p->lchild,deep+1); //递归打印左子树
        PreOrder(p->rchild,deep+1); //递归打印右子树
    }
    return wpl;
}

int main() {
    BiTree pnew; //用来指向新申请的树节点
    BiTree tree=NULL; //tree是指向树根的，代表树
    ptag_t phead=NULL,ptail=NULL,list_pnew=NULL,pcur;
    //层次创建树
    char weight;
    while (scanf("%c",&weight))
    {
        if(weight=='\n')
        {
            break;   //读取换行就结束
        }
        //malloc不可以对空间初始化
        //calloc申请空间大小是两个参数直接相乘，并对空间进行初始化，赋值为0(NULL)
        pnew= (BiTree)calloc(1,sizeof(BiTNode)); //申请的是结构体大小空间，不是结构体指针大小空间
        pnew->weight=weight;
        //给队列结点申请空间
        list_pnew=(ptag_t)calloc(1,sizeof(tag_t));
        list_pnew->p=pnew;
        //如果树是第一个结点
        if(tree==NULL)
        {
            tree=pnew; //tree指向树的根节点
            phead=list_pnew; //第一个结点既是队列头也是队列尾
            ptail=list_pnew;
            pcur=list_pnew; //pcur要指向进入树的父亲元素
        }else{
            //先让元素入队列
            ptail->pnext=list_pnew;
            ptail=list_pnew;
            //接下来把list_pnew结点放入树中
            //pcur->p拿到当前结点，pcur->p->lchild当前结点的左孩子
            if(NULL==pcur->p->lchild)
            {
                pcur->p->lchild=pnew; //pcur->p的左孩子不为空，就放入左孩子中
            } else if(NULL==pcur->p->rchild)
            {
                pcur->p->rchild=pnew; //pcur->p的右孩子不为空，就放入右孩子中
                pcur=pcur->pnext; //当前结点左右孩子都满了，pcur指向下一个结点
            }
        }
    }

    //前序遍历
    printf("-----PreOrder-----\n");
    //1234567
    printf("wpl=%d\n",PreOrder(tree,1));
    return 0;
}
